package everyday.leetcode.editor.cn;

import java.util.HashSet;
import java.util.Set;

/**
 * @Author: Dang Qi
 * @Date: 2021/3/12  11:47
 * @Description:
 * 序列化二叉树的一种方法是使用前序遍历。当我们遇到一个非空节点时，我们可以记录下这个节点的值。如果它是一个空节点，我们可以使用一个标记值记录，例如 #。
 *
 *      _9_
 *     /   \
 *    3     2
 *   / \   / \
 *  4   1  #  6
 * / \ / \   / \
 * # # # #   # #
 * 例如，上面的二叉树可以被序列化为字符串 "9,3,4,#,#,1,#,#,2,#,6,#,#"，其中 # 代表一个空节点。
 *
 * 给定一串以逗号分隔的序列，验证它是否是正确的二叉树的前序序列化。编写一个在不重构树的条件下的可行算法。
 *
 * 每个以逗号分隔的字符或为一个整数或为一个表示 null 指针的 '#' 。
 *
 * 你可以认为输入格式总是有效的，例如它永远不会包含两个连续的逗号，比如 "1,,3" 。
 *
 * 示例 1:
 *
 * 输入: "9,3,4,#,#,1,#,#,2,#,6,#,#"
 * 输出: true
 * 示例 2:
 *
 * 输入: "1,#"
 * 输出: false
 * 示例 3:
 *
 * 输入: "9,#,#,1"
 * 输出: false

 */
public class VerifyPreorderSerializationofABinaryTree {
    public static void main(String[] args) {
        Solution solution = new VerifyPreorderSerializationofABinaryTree().new Solution();
        String s = "9,3,4,#,#,1,#,#,2,#,6,#,#";
        System.out.println(solution.isValidSerialization(s));
    }
    class Solution {
        public boolean isValidSerialization(String preorder) {
            String[] pre = preorder.split(",");

            return isValidSerialization(pre, 0, pre.length);
        }
        // [start, end), 左闭右开
        public boolean isValidSerialization(String[] pre, int start, int end){
            int n = end - start;
            if(n==1 && "#".equals(pre[end-1]))  return true;
            if(n <= 2 || !"#".equals(pre[end-1]) || !"#".equals(pre[end-2]) || "#".equals(pre[start])) return false;

            int digit = 0, sp = 0;
            int i = start + 1;
            while(digit+1!=sp && i < end){
                if("#".equals(pre[i])) sp++;
                else digit++;
                i++;
            }

            if(digit+1!=sp) return false;
            return isValidSerialization(pre, start+1, i) && isValidSerialization(pre, i, end);


        }

    }
}
